// 

#include<unordered_set>
#include<vector>
#include<iostream>

using namespace std;

class Solution {
public:
    vector<vector<int>> ret;
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> track;
        backtrack(track, nums);
        return ret;
    }

    // track 路径
    // nums 保存未进入路径的元素
    void backtrack(vector<int> track, vector<int> nums){
        // 路径已达最长
        if(track.size() == nums.size()){
            ret.push_back(track);
            return;
        }

        for(int i = 0; i < nums.size(); i++){
            // 排除不合法的选择：已进入路径的选择
            if(std::count(track.begin(), track.end(), nums[i]) == 1){
                continue;
            }
            // 做选择
            track.push_back(nums[i]);
            backtrack(track, nums);
            // 取消选择
            track.pop_back();
        }

    }
};
void print(vector<vector<int>> ret){
    for(auto line : ret){
        for(auto col : line){
            cout<<col<<" ";
        }
        cout<<endl;
    }
    cout<<ret.size()<<endl;
}
void test_01(){
    Solution slu;
    vector<int> input = {6,2,-1,8};
    vector<vector<int>> ret = slu.permute(input);
    assert(ret.size() == 24);
    print(ret);
}

int main(){
    test_01();
    
    return 0;
}


